#include<bits/stdc++.h>
using namespace std;
#define int long long

struct node {
	int x, y, step;
};

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int m;
int burned[305][305];
bool vis[305][305];

int ans = -1;

void bfs() {
	queue<node> q;
	q.push({0, 0, 0});
	vis[0][0] = 1;

	while (!q.empty()) {
		node t = q.front();
		q.pop();

		if (burned[t.x][t.y] > 1000) {
			ans = t.step;
			return ;
		}

		for (int i = 0; i < 4; i++) {
			int xx = t.x + dx[i];
			int yy = t.y + dy[i];

			if (xx < 0 || yy < 0 || vis[xx][yy] || t.step + 1 >= burned[xx][yy])
				continue;

			q.push({xx, yy, t.step + 1});
			vis[xx][yy] = 1;
		}
	}
}

signed main() {
	memset(burned, 0x3f, sizeof burned);

	cin >> m;
	int x, y, t;
	while (m--) {
		cin >> x >> y >> t;
		burned[x][y] = min(burned[x][y], t);

		if (x)	burned[x - 1][y] = min(burned[x - 1][y], t);

		burned[x + 1][y] = min(burned[x + 1][y], t);

		if (y)	burned[x][y - 1] = min(burned[x][y - 1], t);

		burned[x][y + 1] = min(burned[x][y + 1], t);
	}

	bfs();
	cout << ans;
	return 0;
}
